package 哈希表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 力扣 18
 *
 * @Author zxl
 * @Date 2022/1/22 21:42
 * @Desc 在一个数组中找到四个元素，使其相加等于target，输出满足条件的target
 */
public class 四数之和 {

    public static void main(String[] args) {
        int[] nums = {-1, 3, 4, -3, 0, -1, 3, -3};
        System.out.println("结果：" + findSumTarget(nums,0));


    }

    /**
     * 俩指针
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> findSumTarget(int[] nums,int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                // 去重
                if (j > i+1 && nums[j] == nums[j-1]){
                    continue;
                }
                int left = j+1;
                int right = nums.length-1;
                while (left < right){
                    if (nums[i] + nums[j] + nums[left] + nums[right] > target){
                        right --;
                    }else if (nums[i] + nums[j] + nums[left] + nums[right] < target){
                        left ++;
                    }else {
                        // 找到了
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        result.add(list);
                        while (left < right && nums[right] == nums[right - 1]){
                            right --;
                        }
                        while (left < right && nums[left] == nums[left + 1]){
                            left ++;
                        }
                        right --;
                        left ++;
                    }
                }

            }

        }
        return result;
    }
}
